1. Field of the Invention
The present invention relates to an image coding system and method used in receiving and transmitting image data through a transmission medium, and further relates to a bit allocation method suitable for use in the orthogonal transform coding of motion picture data and audio data.
2. Description of the Prior Art
In order to hold the transmission rate of image data constant, a feedback method has been conventionally practiced. In this method, after image data is quantized in a specified quantization step, its information content is calculated, and the data is requantized with the quantization step changed so that the information content will become a target value. This method, however, meets difficulties in controlling the information content accurately for motion pictures that require real-time processing. Thus, the method is not suitable especially for equipment related to package media such as digital VTR's (Video Tape Recorders).
Under the above circumstances, coding methods of feed-forward type have been proposed which can relatively easily make the information content of image data within a certain range constant. Examples of the methods include those using an ADRC (Adaptive Dynamic Range Coding) method, a transform coding, or the like. The ADRC method is a block adaptive coding method in which an image is divided into blocks and the average number of bits is adaptively assigned to each block with the bit rate constant by the dynamic range of each block. On the other hand, a coefficient-adaptive coding method is generally known as the method using a transform coding, in which bit distribution is determined for each of transform coefficients resulting from an orthogonal transform of image data so that the bit rate is made constant and the quantization error is minimized relative to the transform coefficients.
However, owing to use of dynamic ranges of blocks as described above, the ADRC method is lower in accuracy of bit allocation to each block than when some statistic such as variance is used, and moreover it does not involve the optimum bit allocation relative to the transform coefficients within a block. On the other hand, the method using the transform coding, although implementing an adaptive bit allocation relative to the transform coefficients, is given no consideration to the bit allocation for each block. In consequence, it cannot be said that the optimum bit allocation is always ensured in either case of the above methods. For example, a publication, "Digital Picture Processing," by A. Rosenfeld and A. C. Kak, Academic Press Inc., 2nd edition, 1982, pp. 116-165, introduces a method of bit allocation using the following formula (1): ##EQU1## (i=0, 1, . . . , N-1) where b(i) is the number of bits assigned to the ith transform coefficient, .sigma.(i).sup.2 is a variance of the ith transform coefficient, and bavr is the average number of bits. N is the total number of transform coefficients; for example, if the transform is a one-dimensional 8-point transform, then N=8, and if it is a two-dimensional 4-point by 4-point transform, then N=4.sup.2 =16. And a is a parameter contained in the following formula that represents a quantization error D: ##EQU2##
The above formula (1) can be obtained as to minimize D subject to the following constraint: ##EQU3##
As described above, the functional form of b(i) is ln.sigma.(i).sup.2 + const. It is to be noted that ##EQU4## is represented hereinafter simply as .SIGMA.b(i).
In the actual bit allocation, there is a restriction such as, for example, "b(i) is an integer within a certain range" as follows: EQU b(i).epsilon.{b.sub.min, b.sub.min +1, . . . ,b.sub.max -1, b.sub.max }(2)
(b.sub.min and b.sub.max are integers)
For this reason, it has conventionally been practiced that after determining the b(i) in real-number calculation using the formula (1), bit allocation is made in a manner as shown below (see Japanese Patent Laid-Open Publication No. 55-57900, 1980), assuming that b.sub.min =0 and b.sub.max =5:
(i) b(i) is calculated by the formula (1). PA1 (ii-1) When there is an i satisfying b(i)&lt;-0.5, ##EQU5## where d1 is determined so as to satisfy .SIGMA.b1(i)=N*bavr. (ii-2) When there is no i satisfying b(i)&lt;-0.5, EQU b1(i)=b(i) PA1 (iii-1) When there is an i satisfying b(i).gtoreq.5.5, ##EQU6## where d2 is determined so as to satisfy .SIGMA.b2(i)=N*bavr. (iii-2) When there is no i satisfying b(i).gtoreq.5.5, EQU b2(i)=b1(i) PA1 (iv) b2(i) is rounded into an integer, bI(i). In addition, an e(i) satisfying the following equation is determined: e(i)=.vertline.bI(i)-b2(i).vertline.. PA1 (v) When .SIGMA.bI(i)&lt;N*bavr, an i that minimizes the e(i) is assumed to be i.sub.min, with additional assumptions: EQU bI(i.sub.min)=bI(i.sub.min)=1 EQU e(i.sub.min)=.vertline.bI(i.sub.min)-b2(i.sub.min).vertline. PA1 (vi) The operation of step (v) is repeated until .SIGMA.bI(i)=N*bavr. PA1 b2(i)={0.85, 1.35, 2.15, 6.65, 5.00} PA1 bI(i)={1, 1, 2, 7, 5} PA1 .SIGMA.bI(i)=16
On the other hand, when .SIGMA.bI(i)&gt;N*bavr, an i that maximizes the rounding error e(i) is assumed to be i.sub.max, with additional assumptions: EQU bI(i.sub.max)=bI(i.sub.max)-1 EQU e(i.sub.max)=.vertline.bI(i.sub.max)-b2(i.sub.max).vertline.
In the above conventional method, there is a possibility that a bit allocation not satisfying the restriction of the above formula (2) be given. For instance, assume that if N=5 and N*bavr=16, then b(i)={-0.40, 0.10, 0.90, 5.40, 10.00} after step (i) is processed. In this case, since there is no value smaller than -0.50, b(i) is assumed to be b1(i) in step (ii-2). In step (iii-1), after the value 10 is set to 5, d2=1.25 is added to the other values so that the total sum becomes 16. As a result,
which in step (iv) leads to:
Consequently, this serves as the bit allocation to be found, whereas bI(3)=7 is larger than 5, inconsistent with the above-mentioned restriction.
To avoid such an inconsistency, it is necessary to check, when the last bit allocation is completed, if all bit allocations are desirable, and then to correct undesirable bit allocations in some way, if any.
There is another possibility, when the above step (v) is effected, that a b(i) which, in step (i), has satisfied the condition below may be such that its functional form is deviated from ln.sigma.(i).sup.2 +const. EQU b(i).epsilon.[b.sub.min, b.sub.max ]